package io.github.tangwan.algorithm;

/**
 * @author tangwan
 * @version V1.0
 * created on 2021/10/8 15:06
 * @since JDK 1.8
 */
public class 无重复字符的最长子串 {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        //System.out.println(lengthOfLongestSubstring("bbbbb"));
        //System.out.println(lengthOfLongestSubstring("pwwkew"));
        //System.out.println(lengthOfLongestSubstring(""));
        //System.out.println(lengthOfLongestSubstring("abcdef"));
        //System.out.println(lengthOfLongestSubstring("AbcdeF1234 56"));

        System.out.println(lengthOfLongestSubstring2("abcabcbb"));
    }

    public static int lengthOfLongestSubstring(String s) {
        int maxChildLen = 0;
        int[] index = new int[128];
        for (int j = 0, i = 0; j < s.length(); j++) {
            i = Math.max(index[s.charAt(j)], i);
            maxChildLen = Math.max(maxChildLen, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return maxChildLen;
    }

    public static int lengthOfLongestSubstring2(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }

}
